package com.wangbo.basic;

import lombok.experimental.UtilityClass;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 针对树的遍历器
 */
@UtilityClass
public class TraverseUtil {
    /**
     * 深度优先遍历-栈实现
     */
    public void depthTraverse(Node root) {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();

            // 访问当前节点
            System.out.printf("%d -> ", node.data);

            // 左右子树入栈
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }

        }
    }

    /**
     * 广度优先遍历-队列实现
     */
    public void broadTraverse(Node root) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();

            System.out.printf("%d -> ", root.data);

            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

    /**
     * 前序遍历-递归实现
     */
    public void preTraverse(Node root) {
        // 基本情形
        if (root == null){
            return;
        }

        // 递归情形
        System.out.printf("%d -> ", root.data); // 访问当前节点
        preTraverse(root.left); // 递归左子树
        preTraverse(root.right); // 递归右子树
    }

    /**
     * 中序遍历-递归实现
     */
    public void middleTraverse(Node root) {
        // 基本情形
        if (root == null) {
            return;
        }

        // 递归情形
        middleTraverse(root.left); // 遍历左子树
        System.out.printf("%d -> ", root.data); // 访问当前节点
        middleTraverse(root.right); // 遍历右子树
    }

    /**
     * 后序遍历-递归实现
     */
    public void postTraverse(Node root) {
        // 基本情形
        if (root == null) {
            return;
        }
        // 递归情形
        postTraverse(root.left);
        postTraverse(root.right);
        System.out.printf("%d -> ", root.data); // 访问当前节点
    }

    /**
     * 蛇形遍历-广度优先+层级坐标+Stack
     * 奇数层从左向右，偶数层从右向左
     */
    public void snakeTraverse(Node root) {
        if (root == null) {
            return;
        }

        Queue<Node> queue = new LinkedList<>();
        Stack<Node> stack = new Stack<>();
        int level = 0; // 层级计数器

        queue.add(root);
        queue.add(null); // 第一层结束符

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node != null) { // 上层出队遍历
                if (level % 2 == 1) { // 此时的 level 是上上层的层级坐标
                    stack.push(node);
                } else {
                    System.out.printf("%d -> ", node.data);
                }

                // 下层入队
                if (node.left != null) { // 这里的null是层结束符，具有特殊含义，必须加非空判断，防止空节点入队
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            } else { // 上层遍历结束
                if (!queue.isEmpty()) { // 如果队列不为空，说明下层存在，并且已经入队，放置结束符
                    queue.add(null);
                }
                if (level % 2 == 1) { // 此时的 level 是上上层的层级坐标
                    while (!stack.isEmpty()) {
                        System.out.printf("%d -> ", stack.pop().data);
                    }
                }
                level++;
            }

        }
    }

}
